//现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为： 
//
// 
// 只能从架子的左上角开始拿珠宝 
// 每次可以移动到右侧或下侧的相邻位置 
// 到达珠宝架子的右下角时，停止拿取 
// 
//
// 注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。 
//
// 
//
// 示例 1： 
//
// 
//输入：frame = [[1,3,1],[1,5,1],[4,2,1]]
//输出：12
//解释：路径 1→3→5→2→1 可以拿到最高价值的珠宝 
//
// 
//
// 提示： 
//
// 
// 0 < frame.length <= 200 
// 0 < frame[0].length <= 200 
// 
//
// 
//
// Related Topics 数组 动态规划 矩阵 👍 554 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-05-16 00:02:53
 * @description LCR 166.珠宝的最高价值
 */
public class LiWuDeZuiDaJieZhiLcof{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 LiWuDeZuiDaJieZhiLcof fun=new LiWuDeZuiDaJieZhiLcof();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int jewelleryValue(int[][] frame) {
		int n = frame[0].length;
		int [] dp=new int[n];

		int m = frame.length;
		for (int i = 0; i < m; i++) {
			dp[0]=dp[0]+frame[i][0];
			for (int j = 1; j < n; j++) {
				dp[j]=frame[i][j]+(i>0?Math.max(dp[j],dp[j-1]):dp[j-1]);
			}
		}
		return dp[n-1];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
